/**
 * 
 */
package ro.dta.idbi.model.dynamicpattern;

import java.util.Arrays;
import java.util.Hashtable;
import java.util.Map;

import ro.dta.idbi.interfaces.IDistMatrixCalculator;
import ro.dta.idbi.interfaces.IGraphIsomorphism;

/**
 * Implementation of the Schmidt-Druffel algorithm to check if two graphs are
 * isomorphic
 * 
 * @author Tudor Dobrila
 * 
 */
public class SDIsomorphism implements IGraphIsomorphism {

	/**
	 * Distance matrix calculator algorithm
	 */
	private IDistMatrixCalculator distAlgorithm;

	/**
	 * Total execution time of the last application of the algorithm
	 */
	private long totalTime;

	/**
	 * Schmidt Druffel graph isomorphism algorithm class constructor
	 * 
	 * @param distAlgorithm
	 *            Distance matrix calculator algorithm to use
	 */
	public SDIsomorphism(IDistMatrixCalculator distAlgorithm) {
		this.distAlgorithm = distAlgorithm;
	}

	@Override
	public int[] areIsomorphic(int[][] graph1, int[][] graph2) {
		if (graph1.length != graph1[0].length || graph1.length != graph2.length
				|| graph1[0].length != graph2[0].length) {
			// Graphs have different no. of vertices
			return null;
		}

		long startTime = System.currentTimeMillis();
		int noVertices = graph1.length;
		double[][] distMatrix1 = distAlgorithm.calculateDistanceMatrix(graph1);
		double[][] distMatrix2 = distAlgorithm.calculateDistanceMatrix(graph2);
		Partition partition = computeInitialPartition(distMatrix1, distMatrix2);

		if (!partition.isClassesEqual()) {
			return null;
		}

		int[] mapped1 = new int[noVertices];
		Arrays.fill(mapped1, -1);
		int[] mapped2 = new int[noVertices];
		Arrays.fill(mapped2, -1);
		int[] crtVertex = new int[noVertices];
		Arrays.fill(crtVertex, -1);

		int[] mapping = this.backtrack(0, noVertices, crtVertex, partition, mapped1, mapped2,
				distMatrix1, distMatrix2);
		totalTime = System.currentTimeMillis() - startTime;

		return mapping;
	}

	/**
	 * Perform the backtracking to identify the mapping between the two graphs,
	 * if one exists
	 * 
	 * @param t
	 *            Current time step
	 * @param noVertices
	 *            Total number of vertices
	 * @param crtVertex
	 *            Array holding the vertex to be considered for each time step
	 * @param p
	 *            Current partition of the vertices
	 * @param crtMapping1
	 *            Current mapping
	 * @param crtMapping2
	 *            Current inverse of the mapping
	 * @param distMatrix1
	 *            Distance matrix of the first graph
	 * @param distMatrix2
	 *            Distance matrix of the second graph
	 * @return A mapping from the vertices of the first graph to the vertices of
	 *         the second graph, <i>null</i> if no such mapping exists
	 */
	private int[] backtrack(int t, int noVertices, int[] crtVertex, Partition p, int[] crtMapping1,
			int[] crtMapping2, double[][] distMatrix1, double[][] distMatrix2) {
		if (t == noVertices) {
			// Graphs are isomorphic
			return crtMapping1;
		}

		int i = crtVertex[t];
		if (i == -1) {
			i = computeNextSource(noVertices, p, crtMapping1);
			crtVertex[t] = i;
		}

		// Choose next vertex from the second graph
		int targetClass = p.getClassAt(0, i);
		int r = computeNextTarget(noVertices, targetClass, p, -1, crtMapping2);
		do {
			// Compose vectors
			DoublePair[] c1_1 = compose(p.getClass(0), distMatrix1[i]);
			DoublePair[] c1_2 = compose(p.getClass(1), distMatrix2[r]);
			int[][] c1 = combine(c1_1, c1_2);
			if (c1 != null) {
				DoublePair[] c2_1 = compose(c1[0], getColumn(distMatrix1, i));
				DoublePair[] c2_2 = compose(c1[1], getColumn(distMatrix2, r));
				int[][] c2 = combine(c2_1, c2_2);
				if (c2 != null) {
					Partition p2 = new Partition(c2);

					if (p2.isClassesEqual()) {
						crtMapping1[i] = r;
						crtMapping2[r] = i;
						int[] mapping = backtrack(t + 1, noVertices, crtVertex, p2, crtMapping1,
								crtMapping2, distMatrix1, distMatrix2);

						if (mapping != null) {
							return mapping;
						}

						crtMapping1[i] = -1;
						crtMapping2[r] = -1;
					}
				}
			}

			r = computeNextTarget(noVertices, targetClass, p, r, crtMapping2);
		} while (r != -1);

		if (r == -1 && t == 0) {
			// Graphs are NOT isomorphic
			return null;
		}

		return null;
	}

	/**
	 * Get the <i>i</i>-th column in a matrix
	 * 
	 * @param matrix
	 *            Matrix for which a column must be retrieved
	 * @param column
	 *            Index of the column to retrieve
	 * @return The <i>-th</i> column in the matrix
	 */
	private static double[] getColumn(double[][] matrix, int column) {
		if (matrix.length == 0) {
			throw new IllegalArgumentException("Only non-empty matrices are valid.");
		}

		if (column >= matrix[0].length) {
			throw new IllegalArgumentException("Column is out of bounds.");
		}

		double[] result = new double[matrix[0].length];
		for (int i = 0; i < matrix.length; i++) {
			result[i] = matrix[i][column];
		}

		return result;
	}

	/**
	 * Compose an integer array with a double array
	 * 
	 * @param array1
	 *            Integer array
	 * @param array2
	 *            Double array
	 * @return Composition of the two arrays
	 */
	private DoublePair[] compose(int[] array1, double[] array2) {
		if (array1.length != array2.length) {
			throw new IllegalArgumentException("Vectors are of different sizes.");
		}

		DoublePair[] result = new DoublePair[array1.length];
		for (int i = 0; i < array1.length; i++) {
			result[i] = new DoublePair(array1[i], array2[i]);
		}

		return result;
	}

	/**
	 * Combine two DoublePair arrays. Every unique term from the two arrays is
	 * substituted with a unique integer
	 * 
	 * @param intPair1
	 *            DoublePair array
	 * @param intPair2
	 *            DoublePair array
	 * @return A matrix with two rows. Each row represents the new class vector
	 *         of each graph. If the two arrays can't be combine, the method
	 *         returns <i>null</i>
	 */
	private int[][] combine(DoublePair[] intPair1, DoublePair[] intPair2) {
		if (intPair1.length != intPair2.length) {
			throw new IllegalArgumentException("Vectors are of different sizes.");
		}

		int crtClass = 1;
		Map<DoublePair, Integer> classes = new Hashtable<DoublePair, Integer>();
		for (int i = 0; i < intPair1.length; i++) {
			if (!classes.containsKey(intPair1[i])) {
				classes.put(intPair1[i], crtClass++);
			}
		}
		for (int i = 0; i < intPair2.length; i++) {
			if (!classes.containsKey(intPair2[i])) {
				return null;
			}
		}

		int[][] result = new int[2][];
		result[0] = new int[intPair1.length];
		result[1] = new int[intPair1.length];

		for (int i = 0; i < intPair1.length; i++) {
			result[0][i] = classes.get(intPair1[i]);
			result[1][i] = classes.get(intPair2[i]);
		}

		return result;
	}

	/**
	 * Choose a vertex from the second graph, that is part of the class
	 * <i>targetClass</i>, has not been mapped yet and has not been previously
	 * considered
	 * 
	 * @param noVertices
	 *            Number of vertices in the graphs
	 * @param targetClass
	 *            Target class
	 * @param p
	 *            Partition in which to look for the vertex
	 * @param lastTarget
	 *            Index of the last considered vertex
	 * @param mapping
	 *            Mapping of the nodes in the second graph
	 * @return Index of the node in the second graph that will be considered
	 *         next
	 */
	private int computeNextTarget(int noVertices, int targetClass, Partition p, int lastTarget,
			int[] mapping) {
		for (int j = lastTarget + 1; j < noVertices; j++) {
			if (p.getClassAt(1, j) == targetClass && mapping[j] == -1) {
				return j;
			}
		}

		return -1;
	}

	/**
	 * Compute the next node in the first graph that has NOT yet been mapped. If
	 * a class exists with a unique unmapped vertex, choose it
	 * 
	 * @param noVertices
	 *            Number of vertices in the graphs
	 * @param partition
	 *            Current partition
	 * @param mapped
	 *            Mapping of the nodes from the first graph
	 * @return Index of the next vertex to be considered
	 */
	private int computeNextSource(int noVertices, Partition partition, int[] mapped) {
		// Search for partitions with only ONE unmapped element
		for (int j = 0; j < noVertices; j++) {
			if (partition.getCountAt(0, j) == 1) {
				for (int k = 0; k < noVertices; k++) {
					if (partition.getClassAt(0, k) == (j + 1) && mapped[k] == -1) {
						return k;
					}
				}
			}
		}

		// If no such partition has been found, pick the first unmapped element
		for (int j = 0; j < noVertices; j++) {
			if (mapped[j] == -1) {
				return j;
			}
		}

		return -1;
	}

	/**
	 * Compute the initial partition of the vertices in the two graphs
	 * 
	 * @param distMatrix1
	 *            Distance matrix of the first graph
	 * @param distMatrix2
	 *            Distance matrix of the second graph
	 * @return Matrix with two rows, first row represents the partition of the
	 *         first graph, second row represents the partition of the second
	 *         graph
	 */
	private Partition computeInitialPartition(double[][] distMatrix1, double[][] distMatrix2) {
		int noVertices = distMatrix1.length;
		DoublePair[][] chMatrix1 = computeCharacteristicMatrix(distMatrix1);
		DoublePair[][] chMatrix2 = computeCharacteristicMatrix(distMatrix2);
		Partition result = new Partition(noVertices);

		// Compute classes
		int crtClass = 0;
		int k;
		do {
			crtClass++;
			k = -1;
			// Find the first unassigned vertex
			for (int i = 0; i < noVertices; i++) {
				if (result.getClassAt(0, i) == 0) {
					k = i;
					break;
				}
			}

			if (k == -1) { // No unassigned vertex left, exit loop
				break;
			}

			// Compute the hash of the k-th row in the characteristic matrix
			int origHash = Arrays.deepHashCode(chMatrix1[k]);
			int count1 = 0, count2 = 0;
			// Search for rows with the same hash
			for (int i = 0; i < noVertices; i++) {
				int crtHash = Arrays.deepHashCode(chMatrix1[i]);
				if (origHash == crtHash && areEqual(chMatrix1[k], chMatrix1[i])) {
					result.setClassAt(0, i, crtClass);
					count1++;
				}

				crtHash = Arrays.deepHashCode(chMatrix2[i]);
				if (origHash == crtHash && areEqual(chMatrix1[k], chMatrix2[i])) {
					result.setClassAt(1, i, crtClass);
					count2++;
				}
			}

			result.setCountAt(0, crtClass - 1, count1);
			result.setCountAt(1, crtClass - 1, count2);
		} while (true);

		return result;
	}

	/**
	 * Check if two IntPair arrays are equal
	 * 
	 * @param array1
	 *            First IntPair array
	 * @param array2
	 *            Second IntPair array
	 * @return True if arrays are equal, false otherwise
	 */
	private boolean areEqual(DoublePair[] array1, DoublePair[] array2) {
		if (array1.length != array2.length) {
			return false;
		}

		for (int i = 0; i < array1.length; i++) {
			if (array1[i].getX() != array2[i].getX() || array1[i].getY() != array2[i].getY()) {
				return false;
			}
		}

		return true;
	}

	/**
	 * Compute the characteristic matrix of a distance matrix
	 * 
	 * @param distMatrix
	 *            Distance matrix of a graph
	 * @return Characteristic matrix of the graph
	 */
	private DoublePair[][] computeCharacteristicMatrix(double[][] distMatrix) {
		int noVertices = distMatrix.length;
		int noCols = distMatrix[0].length;
		DoublePair[][] chMatrix = new DoublePair[noVertices][];
		for (int i = 0; i < noVertices; i++) {
			chMatrix[i] = new DoublePair[noCols];
			for (int j = 0; j < noCols; j++) {
				chMatrix[i][j] = new DoublePair();
			}
		}

		// Compute the row characteristic
		// xr[i][m] = the number of vertices that are at distance m from i
		for (int i = 0; i < noVertices; i++) {
			for (int m = 1; m < noCols; m++) {
				int count = 0;
				for (int j = 0; j < noVertices; j++) {
					if (distMatrix[i][j] == m) {
						count++;
					}
				}
				chMatrix[i][m].setX(count);
			}
		}

		// Compute the column characteristic
		// xc[i][m] = the number of vertices that vertex i is at distance m from
		for (int j = 0; j < noVertices; j++) {
			for (int m = 1; m < noCols; m++) {
				int count = 0;
				for (int i = 0; i < noVertices; i++) {
					if (distMatrix[i][j] == m) {
						count++;
					}
				}
				chMatrix[j][m].setY(count);
			}
		}

		return chMatrix;
	}

	/**
	 * @return Total execution time of the last application
	 */
	public long getTotalTime() {
		return totalTime;
	}
	
}
